package com.leetcode.LC_MED;

public class LC1574 {
    public int findLengthOfShortestSubarray(int[] arr) {

        int n = arr.length;
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left+1]) {
            left++;
        }
        // [0...left]有序
        if (left == n - 1) {
            return 0;
        }
        // [right...n-1]有序
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) {
            right--;
        }

        // 完全删除一边[left+1, n-1], 或者[0...right - 1]
        int result = Math.min(n - left - 1, right);

        // 左边和右边各保留一部分
        int i = 0, j = right;

        while (i <= left && j <= n - 1) {
            if (arr[i] <= arr[j]) {
                // [0...i] 和 [j...n-1] 有序, 删除 [i+1...j-1]
                result = Math.min(result, j - i - 1);
                i++;
            } else {
                // 小的+1
                j++;
            }
        }
        return result;

        /*作者：avlgood2018
        链接：https://leetcode-cn.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/solution/java-jian-dan-on-by-avlgood2018/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
    }
}
